package com.learn;

/**
 * 异或的相关题解，异或等同于二进制位相加，无符号进位的结果，也可以记为相同为0，不同为1，0^N = N N^N=0
 * 找出最右侧为1的算法 N = N&(~N+1)
 */
public class EorDemo {

    /**
     * 数组中有偶数个相同的数，1个不同的数，找出这个不同数，
     * 利用异或运算，偶数个异或结果必等于0，最终异或的结果必等于这个不同数
     *
     * @param arr
     * @return
     */
    public static int demo1(int[] arr) {
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            res = res ^ arr[i];
        }
        return res;
    }

    /**
     * 需求：
     * 数组中有偶数个相同的数，2个奇数个的不同的数，如{1,1,2,2,3,3,3,4,4,4}，
     * 解法：异或的结果为res = a^b      a,b必然在二进制中有一个数的二进制位上不等于1
     * 则可以将数组划分位2组，某一位二进制上为1和不等1的
     *
     * @param arr
     * @return
     */
    public static void demo2(int[] arr) {
        //a^b
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor = eor ^ arr[i];
        }
        //eor = a^b

        //找到最右侧为1的值
        //eor!=0
        //eor必然有一个位置为1
        //01100110
        //00001000
        int rightOne = eor ^ (~eor + 1);
        int eor1 = 0;
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & rightOne) != 0) {
                //只与当前位为1的进行运算
                eor1 =eor1^arr[i];
            }
        }
        //eor1则为其中的一个数，另一个数则等价于eor ^ eor1
        System.out.println(eor1);
        System.out.println(eor ^ eor1);
    }


    public static void main(String[] args) {
        int[] s = {1, 1, 2, 3, 2};
        System.out.println(demo1(s));
        //10 2  11 3
        System.out.println(2^3);
    }
}
